package com.bascker.algorithm.practice.recursion;

/**
 * 斐波那契数列: 数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
 * F(0) = 0, F(1) = 1
 * F(n) = F(n - 1) + F(n - 2), n > 1
 * <p>
 * 其中 0 <= n <= 30
 *
 * @apiNote leetcode T509
 */
public class Fib {

    /**
     * db 数组迭代解法: 自底向上
     * 状态转移方程:
     * 1,                      n < 2
     * dp(n) =
     * dp(n - 1) + dp(n - 2),  n >= 2
     * <p>
     * 时间复杂度: O(n)
     */
    public int fib(int n) {
        // 异常用例保护: 防止 n < 0 时, dp 数组越界
        if (n < 2) {
            return n;
        }

        final int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    /**
     * 备忘录 + 递归解法 ==> 自顶向下(顶是递归树的顶部)
     * 时间复杂度: O(n)
     */
    public int solveByMemorandumBook(final int n) {
        final int[] cache = new int[n + 1];
        return solve(cache, n);
    }

    private int solve(final int[] cache, final int n) {
        // 防止 n = 0 时, 出现 cache[-1] 的场景
        if (n < 2) {
            return n;
        }

        if (cache[n] != 0) {
            return cache[n];
        }

        cache[n] = solve(cache, n - 1) + solve(cache, n - 2);
        return cache[n];
    }


    /**
     * 递归解法
     * 时间复杂度: 子问题个数 * 子问题解的耗时
     * 此处递归树是一颗二叉树，二叉树节点总数为指数级别 O(2^n)
     * 子问题解为 f(n - 1) + f(n - 2), 耗时 O(1)
     * ==> T(n) = O(2^n)
     */
    public int solveByRecursion(int n) {
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        return solveByRecursion(n - 1) + solveByRecursion(n - 2);
    }

}
